package leecode.二叉树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author wangxi created on 2021/5/22 23:12
 * @version v1.0
 *
 * 验证是否完全二叉树
 * 算法
 * 1.层次遍历直至遇到第一个空节点
 * 2.完全二叉树在遇到第一个空节点的时候，后面的所有结果应全为null,否则就是错误的。也就是说
 * 遇到第一个null节点后，队列剩余节点应全为null节点
 *
 *
 * 完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
 * 需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树
 */
public class ValidateCompleteTree {

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null) {
            // 层次遍历，只保留每一层的节点
            TreeNode node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }
        // 当碰到第一个null节点时，后面节点应全为null
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                return false;
            }
        }
        return true;
    }
}
